package 力扣._452_用最少数量的箭引爆气球;

import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int findMinArrowShots(int[][] points) {
        // 按照左边升序排序
        Arrays.sort(points, Comparator.comparingInt(a -> a[0]));
        int ans = 0; // 箭数量
        int i = 0, n = points.length;
        while (i < n ) {
            int a = points[i][0], b = points[i][1]; // 当前的清除范围
            if(i < n-1) {
                i++;
                // 当i对应的区间和[a,b]没有交集时结束
                while (i < n && b >= points[i][0]) {
                    // 将[a,b]更新到和i对应的区间的交集
                    a = Math.max(a, points[i][0]);
                    b = Math.min(b, points[i][1]);
                    i++;
                }
            }else
                i++;
            ans++;
        }
        return ans;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.findMinArrowShots(new int[][]{
//                {10,16},{2,8},{1,6},{7,12}
                {1,2},{3,4},{5,6},{7,8}
        }));
    }
}